<html>
<head><meta charset="utf-8"><title>Why BTreeMap? · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html">Why BTreeMap?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="222972028"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/222972028" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#222972028">(Jan 16 2021 at 09:43)</a>:</h4>
<p>I notice that all the "map" data structures in the HIR use <code>BTreeMap&lt;ID, ...&gt;</code>. Why not a hash map instead? I usually use hash maps for this kind of thing but maybe there's a performance pitfall in here somewhere</p>



<a name="222972101"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/222972101" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#222972101">(Jan 16 2021 at 09:44)</a>:</h4>
<p>A small id is relatively expensive to hash compared to ordered. That may be part of the reason.</p>



<a name="222981418"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/222981418" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#222981418">(Jan 16 2021 at 13:32)</a>:</h4>
<p>Hash maps can make compilations not reproducible, as iterating them will give us random orders of things. So if you need to iterate a map, then you can't use a <code>HashMap</code> in the compiler</p>



<a name="223003051"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/223003051" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#223003051">(Jan 16 2021 at 20:09)</a>:</h4>
<p>To elaborate on what Oli said, iterating over hashmaps gives you items in random order so you would otherwise have to sort it all the time and you may forget, causing sneaky non-reproducible builds.</p>



<a name="223004066"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/223004066" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#223004066">(Jan 16 2021 at 20:20)</a>:</h4>
<p>The compiler does use indexmap in cases where insertion order is sufficient</p>



<a name="223058943"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/223058943" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#223058943">(Jan 17 2021 at 19:31)</a>:</h4>
<p>There's also <code>IndexVec</code> for things like <code>Body::basic_blocks</code> (where you basically have custom index types).</p>



<a name="223070444"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/223070444" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Aman Arora <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#223070444">(Jan 17 2021 at 23:57)</a>:</h4>
<p>Should entities within TypechkResults use BTrees instead of IndexMap/HashMap?</p>



<a name="223097309"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Why%20BTreeMap%3F/near/223097309" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Why.20BTreeMap.3F.html#223097309">(Jan 18 2021 at 09:33)</a>:</h4>
<p>Not if they are never iterated in a way where the order matters. In that case HashMap is faster.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>